#pragma once
#include <iostream>
#include <algorithm>
//#include <assert.h>

using namespace std;

namespace zzzyh
{

	template<class T>
	class listNode
	{
	public:
		//listNode() {}
		listNode(const T& a=T())
		{
			data = a;
		}

		//private:
		listNode* next = nullptr;
		listNode* previous = nullptr;
		T data = T();
	};

	template<class T,class Ref,class Ptr>
	class list_iterator
	{
	public:
		typedef listNode<T> Node;

		Node* cut;
		list_iterator(Node* c)
			:cut(c)
		{}
		Ref operator*()
		{
			return cut->data;
		}

		Ptr operator->()
		{
			return &(cut->data)	;
		}

		list_iterator operator++()
		{
			cut = cut->next;
			return *this;
		}
		list_iterator operator--() {
			cut = cut->previous;
			return *this;
		}

		list_iterator operator++(int)
		{
			cut = cut->next;
			return cut->previous;
		}
		list_iterator operator--(int) {
			cut = cut->previous;
			return cut->previous;
		}
		list_iterator operator+(size_t i) {
			Node* ret = cut;
			while (i != 0)
			{
				ret = ret->next;
				i--;
			}
			return list_iterator(ret);
		}
		list_iterator operator-(size_t i) {
			Node* ret = cut;
			while (i != 0)
			{
				ret = ret->previous;
				i--;
			}
			return list_iterator(ret);
		}

		bool operator!=(list_iterator pos) const
		{
			return cut != pos.cut;
		}

		bool operator==(list_iterator pos) const 
		{
			return cut == pos.cut;
		}
	};

	//template<class T>
	//class list_const_iterator
	//{
	//public:
	//	typedef listNode<T> Node;
	//	Node* cut;
	//	list_const_iterator(Node* c)
	//		:cut(c)
	//	{}
	//	const T& operator*() const
	//	{
	//		return cut->data;
	//	}

	//	const T* operator->() const
	//	{
	//		return &(cut->data);
	//	}

	//	list_const_iterator operator++()
	//	{
	//		cut = cut->next;
	//		return *this;
	//	}
	//	list_const_iterator operator--() {
	//		cut = cut->previous;
	//		return *this;
	//	}

	//	list_const_iterator operator++(int)
	//	{
	//		cut = cut->next;
	//		return cut->previous;
	//	}
	//	list_const_iterator operator--(int) {
	//		cut = cut->previous;
	//		return cut->previous;
	//	}
	//	list_const_iterator operator+(size_t i) {
	//		Node* ret = cut;
	//		while (i != 0)
	//		{
	//			ret = ret->next;
	//			i--;
	//		}
	//		return list_iterator(ret);
	//	}
	//	list_const_iterator operator-(size_t i) {
	//		Node* ret = cut;
	//		while (i != 0)
	//		{
	//			ret = ret->previous;
	//			i--;
	//		}
	//		return list_iterator(ret);
	//	}

	//	bool operator!=(list_const_iterator pos) const
	//	{
	//		return cut != pos.cut;
	//	}

	//	bool operator==(list_const_iterator pos) const
	//	{
	//		return cut == pos.cut;
	//	}
	//};

	template<class T>
	class list
	{
	public:
		typedef listNode<T> Node;
		typedef list_iterator<T,T&,T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;


		void empty_init()
		{
			head = new Node;
			head->next = head;
			head->previous = head;
			sz = 0;
		}
		//typedef list_const_iterator<T> const_iterator;
		list()
		{
			empty_init();
		}

		list(initializer_list<T> li)
		{
			empty_init();
			for (auto& a : li)
			{
				push_back(a);
			}
		}

		void list_swap(list& rem)
		{
			swap(sz,rem.sz);
			swap(head, rem.head);
		}

		list<T>& operator=(const list&s)
		{
			list<T> rem(s);
			list_swap(rem);
			return *this;
		}

		list(const list&s)
		{
			empty_init();
			for (auto &x : s)
			{
				push_back(x);
			}
		}

		~list()
		{
			clear();
			delete head;
		}

		void clear()
		{
			iterator beg = begin();
			while (beg != end())
			{
				beg = erase(beg);
			}
		}

		void push_back(const T& a)
		{
			Node* newNode = new Node(a);
			if (head->next == head) 
			{
				newNode->next = newNode->previous = head;
				head->next = head->previous = newNode;
			}
			else
			{
				newNode->next =  head;
				newNode->previous = head->previous;
				head->previous->next = newNode;
				head->previous = newNode;
			}
			sz++;
			//insert(end(), a);
		}


		iterator begin()
		{
			return iterator(head->next);
		}

		iterator end()
		{
			return iterator(head);
		}

		const_iterator begin() const
		{
			return const_iterator(head->next);
		}

		const_iterator end()const
		{
			return const_iterator(head);
		}


		size_t size()
		{
			return sz;
		}

		void insert(iterator pos, const T& data)
		{
			if (pos == end())
			{
				push_back(data);
				return;
			}
			else {
				Node* newNode = new Node(data);
				if (pos == begin()) {
					newNode->previous = head;
					newNode->next = head->next;
					head->next->previous = newNode;
					head->next = newNode;
				}
				else {
					newNode->previous = pos.cut->previous;
					newNode->next = pos.cut;
					pos.cut->previous->next = newNode;
					pos.cut->previous = newNode;
				}
			}
			sz++;
			/*Node* newNode = new Node(data);
			newNode->previous = pos.cut->previous;
			newNode->next = pos.cut;
			pos.cut->next->previous = newNode;
			pos.cut->next = newNode;*/
		}

		void push_front(const T& a)
		{
			insert(begin(), a);
		}

		iterator erase(iterator pos)
		{
			if (pos.cut == head) {
				return pos;
			}
			Node* left = pos.cut->previous;
			Node* right = pos.cut->next;
			left->next = right;
			right->previous = left;
			delete pos.cut;
			sz--;
			return right;
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		bool empty()
		{
			return sz == 0;
		}

		void print_list()
		{
			iterator beg = begin();
			while (beg!=end())
			{
				cout << *beg << " ";
			}
			cout << endl;
		}

		void print_list() const
		{
			iterator beg = begin();
			while (beg != end())
			{
				cout << *beg << " ";
			}
			cout << endl;
		}

	private:
		Node* head;
		size_t sz = 0;
	};

	template<class Container>
	void print_container(const Container& con)
	{
		for (auto a : con)
		{
			cout << a << " ";
		}
		cout << endl;
	}
}